package sort.insert;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 希尔排序 对简单插入排序的一种改进版本（防止位移次数过多）
 * 不稳定排序
 */
public class Shell {
    public static void main(String[] args) {
        //        int[] arr = {1,8,6,3,4,5,2,7,0,9};
        int[] arr = new int[1000000];
        for (int i = 0; i < 1000000; i++) {
            //0-8000000
            arr[i] = (int)(Math.random() * 1000000);
        }
        System.out.println(arr.length);
        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, 20)));

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        String date1 = simpleDateFormat.format(date);
        System.out.println("排序前的时间=" + date1);
        shell(arr);
        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, 20)));
        System.out.println("排序后的时间=" + simpleDateFormat.format(new Date()));
    }

    /**
     * 移位式
     * @param arr
     */
    public static void shell(int[] arr) {
        //1.设定增量=length/2 向下取整
        // 从一个元素开始每一次步长后的元素是为一组；从第二个元素开始每一次增量后的元素是为一组，以此类推
        // 将每个分组进行排序
        //2.设定步长=length/2/2，同上
        //3.直到步长=1

        for(int d = arr.length / 2;d > 0; d = d/2) {
            //对每组元素进行插入排序。i是【每个分组的第2个-尾部元素】，每往后移一位会切换分组
            for (int i = d; i < arr.length; i++) {
                //定义待插入元素
                int insertVal = arr[i];
                int j;//待插入位置
                if (arr[i] < arr[i-d]) {
                    for (j = i -d; j >=0 && insertVal < arr[j] ; j -= d) {//可视为插入排序的while语句
                        arr[j+d] = arr[j];//符合条件的元素 往后移
                    }
                    //找到待插入位置，即j+d 因为一直和比较元素arr[j]比较，若满足条件则1、比较元素后移，2、j按步长前移
                    //当发现不再满足条件，即找到正确位置即上一轮循环中尚未前移的比较元素的位置，也即前移后的现在的[j]往后移一位的[j+d]
                    arr[j+d] = insertVal;
                }
            }
        }
    }

    /**
     * 交换式
     * @param arr
     */
    public static void shellExchange(int[] arr) {
        //1.设定增量=length/2 向下取整
        // 从一个元素开始每一次步长后的元素是为一组；从第二个元素开始每一次增量后的元素是为一组，以此类推
        // 将每个分组进行排序
        //2.设定步长=length/2/2，同上
        //3.直到步长=1 bmn /

        for(int d = arr.length / 2;d > 0; d = d/2) {
            //对每组元素进行插入排序。i是【每个分组的第2个-尾部元素】，每往后移一位会切换分组
            for (int i = d; i < arr.length; i++) {
                //定义待插入元素
                int insertVal = arr[i];
                int j;//待插入位置
                if (arr[i] < arr[i-d]) {
                    for (j = i -d; j >=0 && insertVal < arr[j] ; j -= d) {//可视为插入排序的while语句
                        arr[j+d] = arr[j];//符合条件的元素 往后移
                    }
                    //找到待插入位置，即j+d 因为一直和比较元素arr[j]比较，若满足条件则1、比较元素后移，2、j按步长前移
                    //当发现不再满足条件，即找到正确位置即上一轮循环中尚未前移的比较元素的位置，也即前移后的现在的[j]往后移一位的[j+d]
                    arr[j+d] = insertVal;
                }
            }
        }
    }
}
